\documentclass[a4paper,11pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage{graphicx}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=2.5cm, right=2.5cm]{geometry} 
\usepackage{float}

%opening
\title{Multi Agent Systems: Project Report}
\author{Roderick Smets, s0194386, Master of Computer Sciences \\ Jef Hermans, s0171748, Master of Artificial Intelligence}

\begin{document}

\maketitle
\newpage



\section{Project development}
In our project we want to build a solution for the pickup-and-delivery problem using the delegate MAS coordination mechanism. The specific part we want to focus on is the optimization (minimization) of the average time till pickup. Further, we would like to check whether more advanced delivery trucks that take into account more than one sequence of pickup-and-delivery would perform better than simple trucks that only consider one sequence of pickup-and-delivery. We assume that a truck can only fit one package at a time.

\subsection{Analysis and requirements}
The domain model containing the key entities of the system can be found in appendix \ref{section:domain_model}.

\subsubsection{Scalability}
General solutions to the PDP problem produce a lot of scalability problems in truck coordination when the amount of trucks in the environment rises. However, since we are building a delegate MAS solution, with decentralized coordination, we can achieve linear scalability in terms of truck count. This is one of the main goals of our system.
\newline
Scalability in terms of package count, however, is much harder to achieve. The amount of packages in the vicinity of a truck can greatly influence the amount of feasible paths. We'll try to manage this through the introduction of locality of package searching. This way we sacrifice some "optimality" of our solution paths for a more scalable system. This approach however introduces another problem: package and/or truck starvation. Our system will address this problem as well, as described later in this report.

\subsubsection{Flexibility}
We decided not to focus on flexibility, but still formulated two flexibility requirements that we feel need to be present in absence of a centralized coordination mechanism. The first is an obvious one; when a truck initially intended to pick up a package, but later decides not to or has a truck-side failure of any kind, this package should still be available for pick up without any intervention from that truck (as it is possible the truck is unable to notify or take the necessary actions in case of this event). The second one pertains to the situation where a truck fails during the delivery process. In that case a package receiver should be able to notice this failure without any truck intervention. Our solution does not have to handle the latter situation explicitly (as in picking up the package left behind) but the design should at least enable this.

\subsubsection{Performance}
As explained above, we can not expect our system to generate completely optimal solutions considering the limited information agents have of their environment. We can however, increase general performance by considering multiple sequences of pick up and delivery of a package. By evaluating paths multiple sequences deep, however, we can allow a truck to make the trade-off between increased distance to the first pick up point but lower distance to the following pick up point. This way, the total distance driven by the trucks will be lower in the average environment. This will, if we casually ignore the possiblity of truck starvation, lead to a lower average pick up time for the packages and thus provide better solutions.

\subsection{Software architectural design}
If we want to build a solution using delegate MAS we need three kind of agents: \textit{resource} agents, \textit{task} agents and \textit{light-weight} agents (ants). The resource agents in our case are the \textit{pickup point} and \textit{dropoff point} agents which extend the general \textit{package point} agent behaviour and are deployed on the devices of respectively the pickup point and dropoff point that could be located on crossroads. The pickup point agent is responsible for sending out feasibility ants that drop pheromone trails in the environment. This agent also has to be able to accept or reject incoming reservations from truck agents. The dropoff point agents handle the behaviour of dropoff points which means that they can accept or reject incoming reservations.

The feasibility ants sent out by the pickup point agents are cloned at every crossroad and drop evaporating feasibility data belonging to one particular package at the road they just travelled till they reach a \textit{specified distance}. The ants stop cloning if they exceed this distance. This is a possible parameter that can be tuned. The feasibility data left in the environment evaporates at a given rate. This rate has to be tuned with respect to the rate at which feasibility ants are sent out by the pickup point agents in order to ensure there is always a pheromone trail in the neighbourhood of the package. If the pickup point agent notices that its package has been collected by a truck, it stops sending feasibility ants and the remaining pheromone trail in the neighbourhood of the package will eventually disappear. This mechanism avoids flooding of the environment with a considerable amount of data and ensures that the feasibility data does not remain in the environment when a package has been picked up. Figure \ref{fig:feas_ants} illustrates the rather limited range of feasibility ants around the packages.

\begin{figure}
\includegraphics[width=1\textwidth]{img/feasibility_ants.eps}
\caption{Illustration of the standard range at which the \textit{feasibility ants} drop feasibility data in the environment. The blue circles represent feasibility ants.}
\label{fig:feas_ants}
\end{figure}

In order to collect data about the environment, truck agents send out scouting exploration ants that do not have any indication about the package locations. They use the \textit{clone-and-spread} strategy at each crossroad they encounter till they reach a \textit{specified maximum number of hops}, a parameter to be tuned. This maximum hop number avoids that a truck agent is exploring the entire environment. An exploration ant can be in two different states, a \textit{searching} state and a \textit{following} state. It starts in the searching state and creates for each type of feasibility data trail an exploration ant of the following state. Note that at this point in time the searching exploration ant does not die, but continues cloning itself till the maximum number of hops has been reached. The following exploration ant follows the pheromone trail of one specific package and stops when it finds the package of which it is following the pheromone trail. At this point the following exploration ant asks the pickup point agent for the path to the dropoff point. The pickup point agent has access to an A* based routing system that determines the path from pickup point to delivery point. With this information the following exploration ant can construct the full path from truck position over package position to dropoff position and reports this path to the agent it has been sent out by. If we consider more than one sequence of pickup-and-delivery, it may be that this agent is a pickup point agent, because if the first pickup-and-delivery sequence is finished, the searching exploration ants are sent out by the pickup point agent at the end position of the first sequence. Figure \ref{fig:exploration_ants} gives an example of a truck agent that is exploring the neighbourhood.
\begin{figure}
\includegraphics[width=1\textwidth]{img/exploration_ants.eps}
\caption{Illustration of the standard range at which the truck agents clone and spread \textit{exploration ants}. The small red circles denote \textit{searching} exploration ants, the small green circles \textit{following} exploration ants. A searching exploration ant creates a following exploration ant as soon as it encounters feasibility data of a package. The packages that will eventually be found by the following exploration ants are surrounded by the blue circles. Hence, the truck agent does not only take into account the closest package, but the closest packages in its neighbourhood. This is needed when we want to make an intention of more pickup-and-delivery sequences.}
\label{fig:exploration_ants}
\end{figure}

In case a truck agent wants to create an intention that consists of for example 3 pickup-and-delivery jobs and it appears to be impossible to make reservations at 3 consecutive pickup and dropoff agents, the truck agent will reexplore his neighbourhood by cloning and spreading searching exploration ants that are looking for a path of 2 pickup-and-delivery jobs. Hence, every time a truck agent does not receive paths with the desired number of pickup-and-delivery jobs, it decreases the desired amount of pickup-and-delivery jobs in 1 path by one. At the same time, the truck agent increases the maximum number of hops a searching exploration ant can travel. This increases the search range of the truck.



The truck agent is modelled using the BDI architecture. The truck agent receives information about the environment from the ants it has sent out and makes up its desires from the following exploration ants that report their followed path and possible corresponding pickup-and-delivery actions to the truck agent. A possible desire could be a pickup-and-delivery of one package or more, in the case we consider more sequences. As a next step, the truck agent goes through a deliberation process in which it takes a decision about which desire it will make as intention with respect to the intention it is currently executing, if one is available. As soon as the truck agent has decided upon the intention to execute, it tries to make a reservation at the pickup and dropoff point agents that correspond to the intention. If the reservation fails at one of the package point agents, the truck agent rejects the chosen intentions and returns to the deliberation phase. If the reservation succeeds, the intention is converted to a plan to execute and this plan is executed in a step by step manner. The reservation itself is made by sending out an intention ant. The truck agent sends out an intention ant that checks whether the path to follow is valid and that hands over a \textit{pickup intention} to the pickup point agent and a \textit{dropoff intention} to the dropoff point agent. The intention ant notifies the truck agent about failure as soon as one of its reserverations has been rejected or, in case of success, as soon as it has reached the end of the path of the intention.

The truck agent can be in two different states based upon the stage of the pickup-and-delivery job. The first state is the \textit{picking up package} state. In this state the truck does not have a package and is driving to the pickup point or trying to make a new intention. The second state is the \textit{delivering package} state in which the trucks holds a package and is driving to its destination and concurrently refreshing its intention. In the case that a reservation of the next pickup-and-delivery job fails, the truck agent ensures that the truck continues its way to the dropoff point of the package it holds. If the package has been dropped, the truck agent starts a new exploration phase to collect information about the environment by sending out new searching exploration ants. We decided to make this division of two states because a division based on making and executing intentions is not possible since this is not clearly separable.
% hier nog iets zeggen over vernieuwen van intenties



\subsection{Implementation}
We reuse the MAS-DisCoSim simulation framework for our implementation. The physical environment (roads, crossroads, trucks) is completely constructed using the yet available entities. However, we extended some existing classes like \texttt{Crossroad}. In this class we store a map with the outgoing roads as keys and \textit{feasibility data stack} as value. This data stack contains the feasibility data on a road for the various packages in the neighbourhood. The \texttt{Truck} class is extended with the ability to deliver and load packages.

The task agent and resource agent are agents that are stored in the original agent layer of the MAS-DisCoSim simulation framework, but the ants and evaporable data (feasibility data, intentions) are not. We decided to store them in a separate \textit{ant layer} that can process ticks at a higher pace than the original agent layer. Also the evaporable data is stored in this layer because this data has to process ticks at the same rate as the ants do. The ant layer is registered at the central virtual clock and can hand out \textit{ant ticks} to the registered entities (ants and evaporable data).


\include{experimentation}
\include{criticalreflection}

\include{projectmanagement}
\include{conclusion}

\appendix
\include{appendix}
\end{document}
